﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//
using InterfaceLibrary;

namespace MergeSort
{
    /*
     *  MergeSort algorithm
     *  source: http://en.csharp-online.net/Merge_Sort
     *  
     *  Implemented as it's own library with minimal changes from
     *  original definition. Comments edited and/or added by 
     *  David Boarman.
     * **/
    public class MergeSorter : ISorter
    {
        #region Fields
        //  Fields

        int[] leftArray;
        int[] rightArray;
        #endregion

        #region Constructors
        //  Constructors

        public MergeSorter ( int[] Source )
        {
            //  create independent copy of array
            leftArray = new int[Source.Length];
            Source.CopyTo(leftArray, 0);

            rightArray = new int[Source.Length];
            Source.CopyTo(rightArray, 0);
        }

        #endregion

        #region Functions
        //  Functions

        /// <summary>
        /// ISorter member. Begins sorting function.
        /// </summary>
        public void Sort ( )
        {
            Sort ( 0, leftArray.Length - 1 );
        }

        // Merge Sort Algorithm
        void Sort ( int left, int right )
        {
            int mid;

            if (right > left)
            {
                mid = ( right + left ) / 2;
                Sort ( left, mid );
                Sort ( mid + 1, right );

                Merge ( left, mid + 1, right );
            }
        }

        void Merge ( int left, int mid, int right )
        {
            int i, left_end, num_elements, tmp_pos;

            left_end = mid - 1;
            tmp_pos = left;
            num_elements = right - left + 1;

            while (( left <= left_end ) && ( mid <= right ))
            {
                if (leftArray[ left ] <= leftArray[ mid ])
                {
                    rightArray[ tmp_pos ] = leftArray[ left ];
                    tmp_pos = tmp_pos + 1;
                    left = left + 1;
                }
                else
                {
                    rightArray[ tmp_pos ] = leftArray[ mid ];
                    tmp_pos = tmp_pos + 1;
                    mid = mid + 1;
                }
            }

            while (left <= left_end)
            {
                rightArray[ tmp_pos ] = leftArray[ left ];
                left = left + 1;
                tmp_pos = tmp_pos + 1;
            }

            while (mid <= right)
            {
                rightArray[ tmp_pos ] = leftArray[ mid ];
                mid = mid + 1;
                tmp_pos = tmp_pos + 1;
            }

            for (i = 0 ; i < num_elements ; i++)
            {
                leftArray[ right ] = rightArray[ right ];
                right = right - 1;
            }
        }
        #endregion

        #region Properties
        //  Properties

        public IEnumerable<int> SortedList
        {
            get { return rightArray; }
        }

        #endregion
    }
}
